home *** CD-ROM | disk | FTP | other *** search
/ Speccy ClassiX 1998 / Speccy ClassiX 98.iso / amiga_system / the_aminet / dev / gcc / ixemulsrc.lha / ixemul-41.4 / gen_library / glob.c < prev    next >
C/C++ Source or Header  |  1995-07-08  |  15KB  |  608 lines
  1. /*
  2.  * Copyright (c) 1989 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Guido van Rossum.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)glob.c    5.12 (Berkeley) 6/24/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  * glob(3) -- a superset of the one defined in POSIX 1003.2.
  43.  *
  44.  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
  45.  *
  46.  * Optional extra services, controlled by flags not defined by POSIX:
  47.  *
  48.  * GLOB_QUOTE:
  49.  *    Escaping convention: \ inhibits any special meaning the following
  50.  *    character might have (except \ at end of string is retained).
  51.  * GLOB_MAGCHAR:
  52.  *    Set in gl_flags if pattern contained a globbing character.
  53.  * gl_matchc:
  54.  *    Number of matches in the current invocation of glob.
  55.  */
  56.  
  57. #define KERNEL
  58. #include "ixemul.h"
  59. #include "kprintf.h"
  60.  
  61. #undef DEBUG
  62.  
  63. #include <sys/cdefs.h>
  64. #include <dirent.h>
  65. #include <glob.h>
  66. #include <ctype.h>
  67. #include <string.h>
  68. #include <stdio.h>
  69. #include <stdlib.h>
  70.  
  71. extern struct dirent *readdir (DIR *);
  72. extern DIR *opendir (char *);
  73.  
  74. #undef NOT    /* in <intuition/intuition.h> on AmigaDOS */
  75.  
  76. #define    DOLLAR        '$'
  77. #define    DOT        '.'
  78. #define    EOS        '\0'
  79. #define    LBRACKET    '['
  80. #define    NOT        '!'
  81. #define    QUESTION    '?'
  82. #define    QUOTE        '\\'
  83. #define    RANGE        '-'
  84. #define    RBRACKET    ']'
  85. #define    SEP        '/'
  86. #define    STAR        '*'
  87. #define    TILDE        '~'
  88. #define    UNDERSCORE    '_'
  89. #define HASH            '#'
  90.  
  91. #define    M_QUOTE        0x8000
  92. #define    M_PROTECT    0x4000
  93. #define    M_MASK        0xffff
  94. #define    M_ASCII        0x00ff
  95.  
  96. #define    CHAR(c)        ((c)&M_ASCII)
  97. #define    META(c)        ((c)|M_QUOTE)
  98. #define    M_ALL        META('*')
  99. #define    M_END        META(']')
  100. #define    M_NOT        META('!')
  101. #define    M_ONE        META('?')
  102. #define    M_RNG        META('-')
  103. #define    M_SET        META('[')
  104. #define    ismeta(c)    (((c)&M_QUOTE) != 0)
  105.  
  106. typedef u_short Char;
  107.  
  108. static int     compare __P((const void *, const void *));
  109. static int     icompare __P((const void *, const void *));
  110. static void     g_Ctoc __P((Char *, char *));
  111. static int     g_lstat __P((Char *, struct stat *));
  112. static DIR    *g_opendir __P((Char *));
  113. static Char    *g_strchr __P((Char *, int));
  114. static int     g_stat __P((Char *, struct stat *));
  115. static int     glob1 __P((Char *, glob_t *));
  116. static int     glob2 __P((Char *, Char *, Char *, glob_t *));
  117. static int     glob3 __P((Char *, Char *, Char *, Char *, glob_t *));
  118. static int     globextend __P((Char *, glob_t *));
  119. static int     match __P((Char *, Char *, Char *, int));
  120. #ifdef DEBUG
  121. static void     qprintf __P((Char *));
  122. #endif
  123.  
  124. /*
  125.  * The main glob() routine: compiles the pattern (optionally processing
  126.  * quotes), calls glob1() to do the real pattern matching, and finally
  127.  * sorts the list (unless unsorted operation is requested).  Returns 0
  128.  * if things went well, nonzero if errors occurred.  It is not an error
  129.  * to find no matches.
  130.  */
  131. glob(pattern, flags, errfunc, pglob)
  132.     const char *pattern;
  133.     int flags, (*errfunc) __P((char *, int));
  134.     glob_t *pglob;
  135. {
  136.     const u_char *compilepat, *patnext;
  137.     int c, err, oldpathc;
  138.     Char *bufnext, *bufend, *compilebuf, *qpatnext, patbuf[MAXPATHLEN+1];
  139.     char *glob_pattern = (char *)pattern;
  140.  
  141.         if (index(pattern, ':'))
  142.           {
  143.             char *colon;
  144.  
  145.             glob_pattern = alloca(strlen(pattern) + 2);
  146.             strcpy(glob_pattern + 1, pattern);
  147.             *glob_pattern = '/';
  148.             colon = index(glob_pattern, ':');
  149.             *colon = '/';
  150.           }
  151.     patnext = (u_char *) glob_pattern;
  152.     if (!(flags & GLOB_APPEND)) {
  153.         pglob->gl_pathc = 0;
  154.         pglob->gl_pathv = NULL;
  155.         if (!(flags & GLOB_DOOFFS))
  156.             pglob->gl_offs = 0;
  157.     }
  158.     pglob->gl_flags = flags & ~GLOB_MAGCHAR;
  159.     pglob->gl_errfunc = errfunc;
  160.     oldpathc = pglob->gl_pathc;
  161.     pglob->gl_matchc = 0;
  162.  
  163.     bufnext = patbuf;
  164.     bufend = bufnext + MAXPATHLEN;
  165.     compilebuf = bufnext;
  166.     compilepat = patnext;
  167.     if (flags & GLOB_QUOTE) {
  168.         /* Protect the quoted characters. */
  169.         while (bufnext < bufend && (c = *patnext++) != EOS) 
  170.             if (c == QUOTE) {
  171.                 if ((c = *patnext++) == EOS) {
  172.                     c = QUOTE;
  173.                     --patnext;
  174.                 }
  175.                 *bufnext++ = c | M_PROTECT;
  176.             }
  177.             else
  178.                 *bufnext++ = c;
  179.     }
  180.     else 
  181.         while (bufnext < bufend && (c = *patnext++) != EOS) 
  182.             *bufnext++ = c;
  183.     *bufnext = EOS;
  184.  
  185.     bufnext = patbuf;
  186.     qpatnext = patbuf;
  187.     /* We don't need to check for buffer overflow any more. */
  188.     while ((c = *qpatnext++) != EOS) {
  189.         switch (c) {
  190.         case LBRACKET:
  191.             pglob->gl_flags |= GLOB_MAGCHAR;
  192.             c = *qpatnext;
  193.             if (c == NOT)
  194.                 ++qpatnext;
  195.             if (*qpatnext == EOS ||
  196.                 g_strchr(qpatnext+1, RBRACKET) == NULL) {
  197.                 *bufnext++ = LBRACKET;
  198.                 if (c == NOT)
  199.                     --qpatnext;
  200.                 break;
  201.             }
  202.             *bufnext++ = M_SET;
  203.             if (c == NOT)
  204.                 *bufnext++ = M_NOT;
  205.             c = *qpatnext++;
  206.             do {
  207.                 *bufnext++ = CHAR(c);
  208.                 if (*qpatnext == RANGE &&
  209.                     (c = qpatnext[1]) != RBRACKET) {
  210.                     *bufnext++ = M_RNG;
  211.                     *bufnext++ = CHAR(c);
  212.                     qpatnext += 2;
  213.                 }
  214.             } while ((c = *qpatnext++) != RBRACKET);
  215.             *bufnext++ = M_END;
  216.             break;
  217.         case QUESTION:
  218.             pglob->gl_flags |= GLOB_MAGCHAR;
  219.             *bufnext++ = M_ONE;
  220.             break;
  221.         case STAR:
  222.             pglob->gl_flags |= GLOB_MAGCHAR;
  223.             *bufnext++ = M_ALL;
  224.             break;
  225.         case HASH:
  226.             if ((flags & GLOB_AMIGA) && *qpatnext == QUESTION)
  227.             {
  228.               qpatnext++;
  229.               pglob->gl_flags |= GLOB_MAGCHAR;
  230.               *bufnext++ = M_ALL;
  231.               break;
  232.             }
  233.             /* fall through */
  234.         default:
  235.             *bufnext++ = CHAR(c);
  236.             break;
  237.         }
  238.     }
  239.     *bufnext = EOS;
  240. #ifdef DEBUG
  241.     qprintf(patbuf);
  242. #endif
  243.  
  244.     if ((err = glob1(patbuf, pglob)) != 0)
  245.         return(err);
  246.  
  247.     if (pglob->gl_pathc == oldpathc && flags & GLOB_NOCHECK) {
  248.         if (!(flags & GLOB_QUOTE)) {
  249.             Char *dp = compilebuf;
  250.             const u_char *sp = pattern;
  251.             while (*dp++ = *sp++);
  252.         }
  253.         else {
  254.             /*
  255.              * Copy pattern, interpreting quotes; this is slightly
  256.              * different than the interpretation of quotes above
  257.              * -- which should prevail?
  258.              */
  259.             while (*pattern != EOS) {
  260.                 if (*pattern == QUOTE) {
  261.                     if (*++pattern == EOS)
  262.                         --pattern;
  263.                 }
  264.                 *compilebuf++ = (u_char)*pattern++;
  265.             }
  266.             *compilebuf = EOS;
  267.         }
  268.         return(globextend(patbuf, pglob));
  269.     } else if (!(flags & GLOB_NOSORT)) 
  270.         qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
  271.             pglob->gl_pathc - oldpathc, sizeof(char *),
  272.                     (flags & GLOB_NOCASE) ? icompare : compare);
  273.     return(0);
  274. }
  275.  
  276. static int
  277. compare(p, q)
  278.     const void *p, *q;
  279. {
  280.     return(strcmp(*(char **)p, *(char **)q));
  281. }
  282.  
  283. static int
  284. icompare(p, q)
  285.     const void *p, *q;
  286. {
  287.     return(strcasecmp(*(char **)p, *(char **)q));
  288. }
  289.  
  290. static
  291. glob1(pattern, pglob)
  292.     Char *pattern;
  293.     glob_t *pglob;
  294. {
  295.     Char pathbuf[MAXPATHLEN+1];
  296.  
  297.     /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
  298.     if (*pattern == EOS)
  299.         return(0);
  300.     return(glob2(pathbuf, pathbuf, pattern, pglob));
  301. }
  302.  
  303. /*
  304.  * The functions glob2 and glob3 are mutually recursive; there is one level
  305.  * of recursion for each segment in the pattern that contains one or more
  306.  * meta characters.
  307.  */
  308. static
  309. glob2(pathbuf, pathend, pattern, pglob)
  310.     Char *pathbuf, *pathend, *pattern;
  311.     glob_t *pglob;
  312. {
  313.     struct stat sb;
  314.     Char *p, *q;
  315.     int anymeta;
  316.  
  317.     /*
  318.      * Loop over pattern segments until end of pattern or until
  319.      * segment with meta character found.
  320.      */
  321.     for (anymeta = 0;;) {
  322.         if (*pattern == EOS) {        /* End of pattern? */
  323.             *pathend = EOS;
  324.             if (g_stat(pathbuf, &sb))
  325.                 return(0);
  326.         
  327.             if (((pglob->gl_flags & GLOB_MARK) &&
  328.                 pathend[-1] != SEP) && (S_ISDIR(sb.st_mode)
  329.                 || (S_ISLNK(sb.st_mode) &&
  330.                 (g_stat(pathbuf, &sb) == 0) &&
  331.                 S_ISDIR(sb.st_mode)))) {
  332.                 *pathend++ = SEP;
  333.                 *pathend = EOS;
  334.             }
  335.             ++pglob->gl_matchc;
  336.             return(globextend(pathbuf, pglob));
  337.         }
  338.  
  339.         /* Find end of next segment, copy tentatively to pathend. */
  340.         q = pathend;
  341.         p = pattern;
  342.         while (*p != EOS && *p != SEP) {
  343.             if (ismeta(*p))
  344.                 anymeta = 1;
  345.             *q++ = *p++;
  346.         }
  347.  
  348.         if (!anymeta) {        /* No expansion, do next segment. */
  349.             pathend = q;
  350.             pattern = p;
  351.             while (*pattern == SEP)
  352.                 *pathend++ = *pattern++;
  353.         } else            /* Need expansion, recurse. */
  354.             return(glob3(pathbuf, pathend, pattern, p, pglob));
  355.     }
  356.     /* NOTREACHED */
  357. }
  358.  
  359. static
  360. glob3(pathbuf, pathend, pattern, restpattern, pglob)
  361.     Char *pathbuf, *pathend, *pattern, *restpattern;
  362.     glob_t *pglob;
  363. {
  364.     register struct dirent *dp;
  365.     DIR *dirp;
  366.     int len, err;
  367.  
  368.     *pathend = EOS;
  369.     errno = 0;
  370.     KPRINTF (("&errno = %lx, errno = %ld\n", &errno, errno));
  371.         
  372.     if (!(dirp = g_opendir(pathbuf)))
  373.         /* TODO: don't call for ENOENT or ENOTDIR? */
  374.         if (pglob->gl_errfunc &&
  375.             (*pglob->gl_errfunc)(pathbuf, errno) ||
  376.             (pglob->gl_flags & GLOB_ERR))
  377.             return(GLOB_ABEND);
  378.         else
  379.             return(0);
  380.  
  381.     err = 0;
  382.  
  383.     /* Search directory for matching names. */
  384.     while ((dp = readdir(dirp))) {
  385.         register u_char *sc;
  386.         register Char *dc;
  387.  
  388.         /* Initial DOT must be matched literally. */
  389.         if (dp->d_name[0] == DOT && *pattern != DOT)
  390.             continue;
  391.         for (sc = (u_char *) dp->d_name, dc = pathend; 
  392.              *dc++ = *sc++;);
  393.         if (!match(pathend, pattern, restpattern, pglob->gl_flags & GLOB_NOCASE)) {
  394.             *pathend = EOS;
  395.             continue;
  396.         }
  397.         err = glob2(pathbuf, --dc, restpattern, pglob);
  398.         if (err)
  399.             break;
  400.     }
  401.  
  402.     /* TODO: check error from readdir? */
  403.     (void)closedir(dirp);
  404.     return(err);
  405. }
  406.  
  407.  
  408. /*
  409.  * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
  410.  * add the new item, and update gl_pathc.
  411.  *
  412.  * This assumes the BSD realloc, which only copies the block when its size
  413.  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
  414.  * behavior.
  415.  *
  416.  * Return 0 if new item added, error code if memory couldn't be allocated.
  417.  *
  418.  * Invariant of the glob_t structure:
  419.  *    Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
  420.  *    gl_pathv points to (gl_offs + gl_pathc + 1) items.
  421.  */
  422. static int
  423. globextend(path, pglob)
  424.     Char *path;
  425.     glob_t *pglob;
  426. {
  427.     register char **pathv;
  428.     register int i;
  429.     u_int newsize;
  430.     char *copy;
  431.     Char *p;
  432.  
  433.     newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
  434.     pathv = (char **)realloc((char *)pglob->gl_pathv, newsize);
  435.     if (pathv == NULL)
  436.         return(GLOB_NOSPACE);
  437.  
  438.     if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
  439.         /* first time around -- clear initial gl_offs items */
  440.         pathv += pglob->gl_offs;
  441.         for (i = pglob->gl_offs; --i >= 0; )
  442.             *--pathv = NULL;
  443.     }
  444.     pglob->gl_pathv = pathv;
  445.  
  446.     for (p = path; *p++;);
  447.     if ((copy = malloc(p - path)) != NULL) {
  448.         g_Ctoc(path, copy);
  449.         pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
  450.     }
  451.     pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
  452.     return(copy == NULL ? GLOB_NOSPACE : 0);
  453. }
  454.  
  455.  
  456. /*
  457.  * pattern matching function for filenames.  Each occurrence of the *
  458.  * pattern causes a recursion level.
  459.  */
  460. static
  461. match(name, pat, patend, nocase)
  462.     register Char *name, *pat, *patend;
  463.     register int nocase;
  464. {
  465.     int ok, negate_range;
  466.     Char c, k;
  467.  
  468.     while (pat < patend) {
  469.         c = *pat++;
  470.         switch (c & M_MASK) {
  471.         case M_ALL:
  472.             if (pat == patend)
  473.                 return(1);
  474.             for (; *name != EOS; ++name)
  475.                 if (match(name, pat, patend, nocase))
  476.                     return(1);
  477.             return(0);
  478.         case M_ONE:
  479.             if (*name++ == EOS)
  480.                 return(0);
  481.             break;
  482.         case M_SET:
  483.             ok = 0;
  484.             k = *name++;
  485.             if (nocase)
  486.               k = tolower(k);
  487.             if (negate_range = ((*pat & M_MASK) == M_NOT))
  488.                 ++pat;
  489.             while (((c = *pat++) & M_MASK) != M_END) {
  490.                     if (nocase)
  491.                             c = tolower(c);
  492.                 if ((*pat & M_MASK) == M_RNG) {
  493.                     if (c <= k && k <= (nocase ? tolower(pat[1]) : pat[1]))
  494.                         ok = 1;
  495.                     pat += 2;
  496.                 } else if (c == k)
  497.                     ok = 1;
  498.                         }
  499.             if (ok == negate_range)
  500.                 return(0);
  501.             break;
  502.         default:
  503.                 if (nocase)
  504.                 {
  505.                   k = *name++;
  506.                   if (tolower(k) != tolower(c))
  507.                     return 0;
  508.                 }
  509.             else if (*name++ != c)
  510.                 return(0);
  511.             break;
  512.         }
  513.     }
  514.     return(*name == EOS);
  515. }
  516.  
  517. /* Free allocated data belonging to a glob_t structure. */
  518. void
  519. globfree(pglob)
  520.     glob_t *pglob;
  521. {
  522.     register int i;
  523.     register char **pp;
  524.  
  525.     if (pglob->gl_pathv != NULL) {
  526.         pp = pglob->gl_pathv + pglob->gl_offs;
  527.         for (i = pglob->gl_pathc; i--; ++pp)
  528.             if (*pp)
  529.                 free(*pp);
  530.         free(pglob->gl_pathv);
  531.     }
  532. }
  533.  
  534. static DIR *
  535. g_opendir(str)
  536.     register Char *str;
  537. {
  538.     char buf[MAXPATHLEN];
  539.  
  540.     if (!*str)
  541.         return(opendir("."));
  542.     g_Ctoc(str, buf);
  543.     return(opendir(buf));
  544. }
  545.  
  546. static int
  547. g_lstat(fn, sb)
  548.     register Char *fn;
  549.     struct stat *sb;
  550. {
  551.     char buf[MAXPATHLEN];
  552.  
  553.     g_Ctoc(fn, buf);
  554.     return(lstat(buf, sb));
  555. }
  556.  
  557. static int
  558. g_stat(fn, sb)
  559.     register Char *fn;
  560.     struct stat *sb;
  561. {
  562.     char buf[MAXPATHLEN];
  563.  
  564.     g_Ctoc(fn, buf);
  565.     return(stat(buf, sb));
  566. }
  567.  
  568. static Char *
  569. g_strchr(str, ch)
  570.     Char *str;
  571.     int ch;
  572. {
  573.     do {
  574.         if (*str == ch)
  575.             return (str);
  576.     } while (*str++);
  577.     return (NULL);
  578. }
  579.  
  580. static void
  581. g_Ctoc(str, buf)
  582.     register Char *str;
  583.     char *buf;
  584. {
  585.     register char *dc;
  586.  
  587.     for (dc = buf; *dc++ = *str++;);
  588. }
  589.  
  590. #ifdef DEBUG
  591. static void 
  592. qprintf(s)
  593.     register Char *s;
  594. {
  595.     register Char *p;
  596.  
  597.     for (p = s; *p; p++)
  598.         (void)printf("%c", *p & 0xff);
  599.     (void)printf("\n");
  600.     for (p = s; *p; p++)
  601.         (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
  602.     (void)printf("\n");
  603.     for (p = s; *p; p++)
  604.         (void)printf("%c", *p & M_META ? '_' : ' ');
  605.     (void)printf("\n");
  606. }
  607. #endif
  608.